1. Field of the Invention
This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to code restructuring.
2. Description of the Related Art
Advances in processor designs have provided very high speed instruction processing. In order to sustain this speed, processors need very effective usage of the memory hierarchy of the machines. Ensuring effective usage is difficult for large programs like compilers or database engine codes that have complex control flow. This occurs, for example, as a result of having to consider inputs of different types or handle error conditions appropriately. Consequently, code generated for large complex programs consists of sections that are heavily executed intermingled with sections that are infrequently executed, resulting in poor utilization of the memory hierarchy. Code restructuring may improve memory hierarchy utilization and, consequently, performance.
The state of the art of code restructuring techniques is described in Simons (B. Simons, "Code Positioning for Procedures and Basic Blocks," IBM Technical Report ADTI-1994-006; also available as IBM Santa Teresa Laboratory Technical Report TR 03.580.). Two representative techniques described by Simons include the IBM Heatshrink and the IBM AOPT products. Heatshrink, a trace-directed program restructuring (TDPR) tool, was designed and implemented by Randy R. Heisch. A more detailed description of Heatshrink is given in Heisch (R. R. Heisch, "Trace-Directed Program Restructuring for AIX Executables", IBM Journal of Research and Development, vol. 38, September 1994.). AOPT, a stand-alone tool developed by Itai Nahshon, attempts to locate a "hot path" in the code and then move the entire path as a single entity, rather than move individual basic blocks. Profile information, used by both Heatshrink and AOPT, is obtained by AOPT. Profiling involves running code using sample or representative inputs. Based on the behavior of the code on the given inputs, one makes assumption about its behavior on all inputs. Heatshrink and AOPT both perform global reordering of basic blocks and are bundled together as part of FDPR (Feedback Directed Program Restructuring tool), an IBM Licensed Program Product for IBM AIX Operating System, Version 4.1.
Pettis et al. (K. Pettis and R. C. Hansen, "Profile Guided Code Positioning," Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation (PLDI), pp. 16-27, June 1990.) follow a different approach, that also relies on profiling information, but that moves executed basic blocks only within a procedure in addition to moving procedures. Basic blocks that are not executed according to the profile data are moved to a separate region at the end of an ordering.
These and other conventional techniques for code restructuring attempt to keep frequently executed code close together in memory. Intuitively, such an approach tries to retain the working set of frequently executed code in cache. If the working set fits in the cache, this approach is reasonable; on the other hand, if the cache is small or if the effective portion of the cache available to an application is small due to multiprogramming, conventional code restructuring techniques may not perform well. A major flaw of these conventional approaches is that "closeness" in memory does not actually relate to cache or paging performance. Two basic blocks may be "close" together in memory, and yet there may still be a cache miss or page fault transitioning between the two basic blocks, or they may be very far apart and still cause the same effect of a cache miss or page fault. Thus, conventional code restructuring techniques fail to realize that blocks interacting frequently should be kept in the same cache line or page rather than "close" to each other in memory. Conventional code restructuring techniques also fail to realize that memory hierarchy hardware parameters such as cache line size, page size, cache associativity size and translation lookaside buffer (TLB) size may be considered in determining the code structure of an application.
Thus, the conventional code restructuring techniques fail to consider memory hierarchy. As such, there is a need for a method of, system for, and computer program product for, providing code restructuring dependent upon a memory hierarchy.